package com.wwz.leetcode;

import com.wwz.common.ListNode;
import org.junit.Test;

/**
 * 给你链表的头节点 head ，每k个节点一组进行翻转，请你返回修改后的链表。
 *
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。
 */
public class LeetCode25 {

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode();
        hair.next = head;
        ListNode pre = hair;
        while (head != null) {
            ListNode tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; i++) {
                tail = tail.next;
                // 不够就直接 返回
                if (tail == null) {
                    return hair.next;
                }
            }
            // 反转head 到 tail 链表
            ListNode[] reverseList = reverseList(head, tail);
            // 新的head 节点
            head = reverseList[0];
            // 新的tail
            tail = reverseList[1];

            // pre 永远指向head之前
            pre.next = head;
            // 准备下一次遍历
            pre = tail;
            head = tail.next;

        }
        return hair.next;
    }

    // 反转到 tail 停止
    public ListNode[] reverseList(ListNode head, ListNode tail) {
        // prev 相当于 等会要去链接的头
        ListNode prev = tail.next;
        ListNode cur = head;
        while (prev != tail) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return new ListNode[]{tail, head};
    }


    @Test
    public void test() {

        ListNode listNode5 = new ListNode(5, null);
        ListNode listNode4 = new ListNode(4, listNode5);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        ListNode res = reverseKGroup(listNode1, 2);
        while (res != null) {
            System.out.println(res.val);
            res = res.next;
        }
    }
}
